package 搜索算法.深度优先搜索;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1. 问题描述
 *      找出一个数组的所有子集
 *
 * 2. 算法分析
 *      递归+回溯
 *      可以利用数组的元素的组合，只不过组合的题目长度是给定的，而对于集合的子集
 *      我们需要找到长度为0，1，2，...,n的所有组合
 *      所以只需要实现n次组合方式即可，对于长度为0，即空集，我们直接初始化到结果集合中即可
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 找到所有的子集 {
    public static void main(String[] args) {

    }


    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        List<Integer> temp = new ArrayList<>();
        res.add(new ArrayList<>()); //将空集合放置到res中
        for(int i = 1; i <= nums.length; i++) {
            perumte(nums,i,res,temp,0,visited); //找到所有i组合
            Arrays.fill(visited,false);
        }
        return res;
    }
    // 找到数组中的长度为k的所有组合
    public void perumte(int[] nums,int k,List<List<Integer>> res,List<Integer> temp,int start,boolean[] visited) {
        dfs(nums,k,res,temp,0,visited);
    }
    // dfs
    public void dfs(int[] nums,int k,List<List<Integer>> res,List<Integer> temp,int start,boolean[] visited) {
        if(temp.size() == k) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for(int j = start; j < nums.length; j++) {
            if(visited[j]==false) {
                visited[j] = true;
                temp.add(nums[j]);
                dfs(nums,k,res,temp,j+1,visited); // 递归
                visited[j] = false;  // 回溯
                temp.remove(temp.size()-1); // 回溯
            }
        }
    }

    // 暴力法
    public static List<List<Integer>> subsets2(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        int len = nums.length;
        if(len == 0) {
            return res;
        }
        for(Integer num : nums) {
            // 依次将res中的集合与当前集合合并
            int size = res.size();
            for(int i = 0; i < size; i++) {
                List<Integer> temp = new ArrayList<>(res.get(i));
                temp.add(num);
                res.add(temp);
            }
        }
        return res;
    }
}